home *** CD-ROM | disk | FTP | other *** search
/ Clickx 115 / Clickx 115.iso / software / tools / windows / tails-i386-0.16.iso / live / filesystem.squashfs / usr / lib / python2.6 / _abcoll.py < prev    next >
Encoding:
Python Source  |  2010-12-26  |  13.6 KB  |  577 lines
  1. # Copyright 2007 Google, Inc. All Rights Reserved.
  2. # Licensed to PSF under a Contributor Agreement.
  3.  
  4. """Abstract Base Classes (ABCs) for collections, according to PEP 3119.
  5.  
  6. DON'T USE THIS MODULE DIRECTLY!  The classes here should be imported
  7. via collections; they are defined here only to alleviate certain
  8. bootstrapping issues.  Unit tests are in test_collections.
  9. """
  10.  
  11. from abc import ABCMeta, abstractmethod
  12. import sys
  13.  
  14. __all__ = ["Hashable", "Iterable", "Iterator",
  15.            "Sized", "Container", "Callable",
  16.            "Set", "MutableSet",
  17.            "Mapping", "MutableMapping",
  18.            "MappingView", "KeysView", "ItemsView", "ValuesView",
  19.            "Sequence", "MutableSequence",
  20.            ]
  21.  
  22. ### ONE-TRICK PONIES ###
  23.  
  24. def _hasattr(C, attr):
  25.     try:
  26.         return any(attr in B.__dict__ for B in C.__mro__)
  27.     except AttributeError:
  28.         # Old-style class
  29.         return hasattr(C, attr)
  30.  
  31.  
  32. class Hashable:
  33.     __metaclass__ = ABCMeta
  34.  
  35.     @abstractmethod
  36.     def __hash__(self):
  37.         return 0
  38.  
  39.     @classmethod
  40.     def __subclasshook__(cls, C):
  41.         if cls is Hashable:
  42.             try:
  43.                 for B in C.__mro__:
  44.                     if "__hash__" in B.__dict__:
  45.                         if B.__dict__["__hash__"]:
  46.                             return True
  47.                         break
  48.             except AttributeError:
  49.                 # Old-style class
  50.                 if getattr(C, "__hash__", None):
  51.                     return True
  52.         return NotImplemented
  53.  
  54.  
  55. class Iterable:
  56.     __metaclass__ = ABCMeta
  57.  
  58.     @abstractmethod
  59.     def __iter__(self):
  60.         while False:
  61.             yield None
  62.  
  63.     @classmethod
  64.     def __subclasshook__(cls, C):
  65.         if cls is Iterable:
  66.             if _hasattr(C, "__iter__"):
  67.                 return True
  68.         return NotImplemented
  69.  
  70. Iterable.register(str)
  71.  
  72.  
  73. class Iterator(Iterable):
  74.  
  75.     @abstractmethod
  76.     def next(self):
  77.         raise StopIteration
  78.  
  79.     def __iter__(self):
  80.         return self
  81.  
  82.     @classmethod
  83.     def __subclasshook__(cls, C):
  84.         if cls is Iterator:
  85.             if _hasattr(C, "next"):
  86.                 return True
  87.         return NotImplemented
  88.  
  89.  
  90. class Sized:
  91.     __metaclass__ = ABCMeta
  92.  
  93.     @abstractmethod
  94.     def __len__(self):
  95.         return 0
  96.  
  97.     @classmethod
  98.     def __subclasshook__(cls, C):
  99.         if cls is Sized:
  100.             if _hasattr(C, "__len__"):
  101.                 return True
  102.         return NotImplemented
  103.  
  104.  
  105. class Container:
  106.     __metaclass__ = ABCMeta
  107.  
  108.     @abstractmethod
  109.     def __contains__(self, x):
  110.         return False
  111.  
  112.     @classmethod
  113.     def __subclasshook__(cls, C):
  114.         if cls is Container:
  115.             if _hasattr(C, "__contains__"):
  116.                 return True
  117.         return NotImplemented
  118.  
  119.  
  120. class Callable:
  121.     __metaclass__ = ABCMeta
  122.  
  123.     @abstractmethod
  124.     def __call__(self, *args, **kwds):
  125.         return False
  126.  
  127.     @classmethod
  128.     def __subclasshook__(cls, C):
  129.         if cls is Callable:
  130.             if _hasattr(C, "__call__"):
  131.                 return True
  132.         return NotImplemented
  133.  
  134.  
  135. ### SETS ###
  136.  
  137.  
  138. class Set(Sized, Iterable, Container):
  139.     """A set is a finite, iterable container.
  140.  
  141.     This class provides concrete generic implementations of all
  142.     methods except for __contains__, __iter__ and __len__.
  143.  
  144.     To override the comparisons (presumably for speed, as the
  145.     semantics are fixed), all you have to do is redefine __le__ and
  146.     then the other operations will automatically follow suit.
  147.     """
  148.  
  149.     def __le__(self, other):
  150.         if not isinstance(other, Set):
  151.             return NotImplemented
  152.         if len(self) > len(other):
  153.             return False
  154.         for elem in self:
  155.             if elem not in other:
  156.                 return False
  157.         return True
  158.  
  159.     def __lt__(self, other):
  160.         if not isinstance(other, Set):
  161.             return NotImplemented
  162.         return len(self) < len(other) and self.__le__(other)
  163.  
  164.     def __gt__(self, other):
  165.         if not isinstance(other, Set):
  166.             return NotImplemented
  167.         return other < self
  168.  
  169.     def __ge__(self, other):
  170.         if not isinstance(other, Set):
  171.             return NotImplemented
  172.         return other <= self
  173.  
  174.     def __eq__(self, other):
  175.         if not isinstance(other, Set):
  176.             return NotImplemented
  177.         return len(self) == len(other) and self.__le__(other)
  178.  
  179.     def __ne__(self, other):
  180.         return not (self == other)
  181.  
  182.     @classmethod
  183.     def _from_iterable(cls, it):
  184.         '''Construct an instance of the class from any iterable input.
  185.  
  186.         Must override this method if the class constructor signature
  187.         does not accept an iterable for an input.
  188.         '''
  189.         return cls(it)
  190.  
  191.     def __and__(self, other):
  192.         if not isinstance(other, Iterable):
  193.             return NotImplemented
  194.         return self._from_iterable(value for value in other if value in self)
  195.  
  196.     def isdisjoint(self, other):
  197.         for value in other:
  198.             if value in self:
  199.                 return False
  200.         return True
  201.  
  202.     def __or__(self, other):
  203.         if not isinstance(other, Iterable):
  204.             return NotImplemented
  205.         chain = (e for s in (self, other) for e in s)
  206.         return self._from_iterable(chain)
  207.  
  208.     def __sub__(self, other):
  209.         if not isinstance(other, Set):
  210.             if not isinstance(other, Iterable):
  211.                 return NotImplemented
  212.             other = self._from_iterable(other)
  213.         return self._from_iterable(value for value in self
  214.                                    if value not in other)
  215.  
  216.     def __xor__(self, other):
  217.         if not isinstance(other, Set):
  218.             if not isinstance(other, Iterable):
  219.                 return NotImplemented
  220.             other = self._from_iterable(other)
  221.         return (self - other) | (other - self)
  222.  
  223.     # Sets are not hashable by default, but subclasses can change this
  224.     __hash__ = None
  225.  
  226.     def _hash(self):
  227.         """Compute the hash value of a set.
  228.  
  229.         Note that we don't define __hash__: not all sets are hashable.
  230.         But if you define a hashable set type, its __hash__ should
  231.         call this function.
  232.  
  233.         This must be compatible __eq__.
  234.  
  235.         All sets ought to compare equal if they contain the same
  236.         elements, regardless of how they are implemented, and
  237.         regardless of the order of the elements; so there's not much
  238.         freedom for __eq__ or __hash__.  We match the algorithm used
  239.         by the built-in frozenset type.
  240.         """
  241.         MAX = sys.maxint
  242.         MASK = 2 * MAX + 1
  243.         n = len(self)
  244.         h = 1927868237 * (n + 1)
  245.         h &= MASK
  246.         for x in self:
  247.             hx = hash(x)
  248.             h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
  249.             h &= MASK
  250.         h = h * 69069 + 907133923
  251.         h &= MASK
  252.         if h > MAX:
  253.             h -= MASK + 1
  254.         if h == -1:
  255.             h = 590923713
  256.         return h
  257.  
  258. Set.register(frozenset)
  259.  
  260.  
  261. class MutableSet(Set):
  262.  
  263.     @abstractmethod
  264.     def add(self, value):
  265.         """Add an element."""
  266.         raise NotImplementedError
  267.  
  268.     @abstractmethod
  269.     def discard(self, value):
  270.         """Remove an element.  Do not raise an exception if absent."""
  271.         raise NotImplementedError
  272.  
  273.     def remove(self, value):
  274.         """Remove an element. If not a member, raise a KeyError."""
  275.         if value not in self:
  276.             raise KeyError(value)
  277.         self.discard(value)
  278.  
  279.     def pop(self):
  280.         """Return the popped value.  Raise KeyError if empty."""
  281.         it = iter(self)
  282.         try:
  283.             value = next(it)
  284.         except StopIteration:
  285.             raise KeyError
  286.         self.discard(value)
  287.         return value
  288.  
  289.     def clear(self):
  290.         """This is slow (creates N new iterators!) but effective."""
  291.         try:
  292.             while True:
  293.                 self.pop()
  294.         except KeyError:
  295.             pass
  296.  
  297.     def __ior__(self, it):
  298.         for value in it:
  299.             self.add(value)
  300.         return self
  301.  
  302.     def __iand__(self, it):
  303.         for value in (self - it):
  304.             self.discard(value)
  305.         return self
  306.  
  307.     def __ixor__(self, it):
  308.         if not isinstance(it, Set):
  309.             it = self._from_iterable(it)
  310.         for value in it:
  311.             if value in self:
  312.                 self.discard(value)
  313.             else:
  314.                 self.add(value)
  315.         return self
  316.  
  317.     def __isub__(self, it):
  318.         for value in it:
  319.             self.discard(value)
  320.         return self
  321.  
  322. MutableSet.register(set)
  323.  
  324.  
  325. ### MAPPINGS ###
  326.  
  327.  
  328. class Mapping(Sized, Iterable, Container):
  329.  
  330.     @abstractmethod
  331.     def __getitem__(self, key):
  332.         raise KeyError
  333.  
  334.     def get(self, key, default=None):
  335.         try:
  336.             return self[key]
  337.         except KeyError:
  338.             return default
  339.  
  340.     def __contains__(self, key):
  341.         try:
  342.             self[key]
  343.         except KeyError:
  344.             return False
  345.         else:
  346.             return True
  347.  
  348.     def iterkeys(self):
  349.         return iter(self)
  350.  
  351.     def itervalues(self):
  352.         for key in self:
  353.             yield self[key]
  354.  
  355.     def iteritems(self):
  356.         for key in self:
  357.             yield (key, self[key])
  358.  
  359.     def keys(self):
  360.         return list(self)
  361.  
  362.     def items(self):
  363.         return [(key, self[key]) for key in self]
  364.  
  365.     def values(self):
  366.         return [self[key] for key in self]
  367.  
  368.     # Mappings are not hashable by default, but subclasses can change this
  369.     __hash__ = None
  370.  
  371.     def __eq__(self, other):
  372.         if not isinstance(other, Mapping):
  373.             return NotImplemented
  374.         return dict(self.items()) == dict(other.items())
  375.  
  376.     def __ne__(self, other):
  377.         return not (self == other)
  378.  
  379. class MappingView(Sized):
  380.  
  381.     def __init__(self, mapping):
  382.         self._mapping = mapping
  383.  
  384.     def __len__(self):
  385.         return len(self._mapping)
  386.  
  387.  
  388. class KeysView(MappingView, Set):
  389.  
  390.     def __contains__(self, key):
  391.         return key in self._mapping
  392.  
  393.     def __iter__(self):
  394.         for key in self._mapping:
  395.             yield key
  396.  
  397.  
  398. class ItemsView(MappingView, Set):
  399.  
  400.     def __contains__(self, item):
  401.         key, value = item
  402.         try:
  403.             v = self._mapping[key]
  404.         except KeyError:
  405.             return False
  406.         else:
  407.             return v == value
  408.  
  409.     def __iter__(self):
  410.         for key in self._mapping:
  411.             yield (key, self._mapping[key])
  412.  
  413.  
  414. class ValuesView(MappingView):
  415.  
  416.     def __contains__(self, value):
  417.         for key in self._mapping:
  418.             if value == self._mapping[key]:
  419.                 return True
  420.         return False
  421.  
  422.     def __iter__(self):
  423.         for key in self._mapping:
  424.             yield self._mapping[key]
  425.  
  426.  
  427. class MutableMapping(Mapping):
  428.  
  429.     @abstractmethod
  430.     def __setitem__(self, key, value):
  431.         raise KeyError
  432.  
  433.     @abstractmethod
  434.     def __delitem__(self, key):
  435.         raise KeyError
  436.  
  437.     __marker = object()
  438.  
  439.     def pop(self, key, default=__marker):
  440.         try:
  441.             value = self[key]
  442.         except KeyError:
  443.             if default is self.__marker:
  444.                 raise
  445.             return default
  446.         else:
  447.             del self[key]
  448.             return value
  449.  
  450.     def popitem(self):
  451.         try:
  452.             key = next(iter(self))
  453.         except StopIteration:
  454.             raise KeyError
  455.         value = self[key]
  456.         del self[key]
  457.         return key, value
  458.  
  459.     def clear(self):
  460.         try:
  461.             while True:
  462.                 self.popitem()
  463.         except KeyError:
  464.             pass
  465.  
  466.     def update(self, other=(), **kwds):
  467.         if isinstance(other, Mapping):
  468.             for key in other:
  469.                 self[key] = other[key]
  470.         elif hasattr(other, "keys"):
  471.             for key in other.keys():
  472.                 self[key] = other[key]
  473.         else:
  474.             for key, value in other:
  475.                 self[key] = value
  476.         for key, value in kwds.items():
  477.             self[key] = value
  478.  
  479.     def setdefault(self, key, default=None):
  480.         try:
  481.             return self[key]
  482.         except KeyError:
  483.             self[key] = default
  484.         return default
  485.  
  486. MutableMapping.register(dict)
  487.  
  488.  
  489. ### SEQUENCES ###
  490.  
  491.  
  492. class Sequence(Sized, Iterable, Container):
  493.     """All the operations on a read-only sequence.
  494.  
  495.     Concrete subclasses must override __new__ or __init__,
  496.     __getitem__, and __len__.
  497.     """
  498.  
  499.     @abstractmethod
  500.     def __getitem__(self, index):
  501.         raise IndexError
  502.  
  503.     def __iter__(self):
  504.         i = 0
  505.         try:
  506.             while True:
  507.                 v = self[i]
  508.                 yield v
  509.                 i += 1
  510.         except IndexError:
  511.             return
  512.  
  513.     def __contains__(self, value):
  514.         for v in self:
  515.             if v == value:
  516.                 return True
  517.         return False
  518.  
  519.     def __reversed__(self):
  520.         for i in reversed(range(len(self))):
  521.             yield self[i]
  522.  
  523.     def index(self, value):
  524.         for i, v in enumerate(self):
  525.             if v == value:
  526.                 return i
  527.         raise ValueError
  528.  
  529.     def count(self, value):
  530.         return sum(1 for v in self if v == value)
  531.  
  532. Sequence.register(tuple)
  533. Sequence.register(basestring)
  534. Sequence.register(buffer)
  535. Sequence.register(xrange)
  536.  
  537.  
  538. class MutableSequence(Sequence):
  539.  
  540.     @abstractmethod
  541.     def __setitem__(self, index, value):
  542.         raise IndexError
  543.  
  544.     @abstractmethod
  545.     def __delitem__(self, index):
  546.         raise IndexError
  547.  
  548.     @abstractmethod
  549.     def insert(self, index, value):
  550.         raise IndexError
  551.  
  552.     def append(self, value):
  553.         self.insert(len(self), value)
  554.  
  555.     def reverse(self):
  556.         n = len(self)
  557.         for i in range(n//2):
  558.             self[i], self[n-i-1] = self[n-i-1], self[i]
  559.  
  560.     def extend(self, values):
  561.         for v in values:
  562.             self.append(v)
  563.  
  564.     def pop(self, index=-1):
  565.         v = self[index]
  566.         del self[index]
  567.         return v
  568.  
  569.     def remove(self, value):
  570.         del self[self.index(value)]
  571.  
  572.     def __iadd__(self, values):
  573.         self.extend(values)
  574.         return self
  575.  
  576. MutableSequence.register(list)
  577.